// 相同的入参则返回缓存的结果。 注意入参是有顺序的，比如一开始可能是 1 2 3，第二次可能是 1 3 2，这是两种不同的入参，那么就**要求我们记录入参的顺序，并且同时记录 以这个顺序入参的结果** 
// 可以想象一下，调用函数三次，入参分别是 `1 2 3` 、 `1 3 2` 、 `1 2 4`， 是不是可以想象成这是一颗树
// 根据这个特性，我们可以根据每次的入参，构造树，以这些入参为例： 1 2 3，1 3 2， 1 2 4， 2 2 4。
//       1            2
//   2      3         2
// 3  4       2       4
// 这些子树有一个统一的根节点，代表的是`无入参时`的缓存结果。
// 有了这些树，当我们遇到了相同的入参，就顺着这个数来查找节点，找到对应的节点，看看它缓存的结果。
// 需要注意的是，**入参数量是不固定的**，可能入参 0 ~ n 个，所以要求我们每个树节点都需要存储对应的缓存值。
// 每个节点是这样的构造：  `[树节点，该节点对应的结果值]`
// 在JS中，符合这样的构造的数据类型就是Map， 键是入参，值是` [树Map，该节点对应的结果值] ` 
type Fn = (...params: any) => any
/**树Map */
type CacheMap = Map<any, CacheNode>
/**缓存树的节点类型元组，第一个是Map，若有结果，则第二个为结果  (也就是元组长度为2时，代表有结果) */
type CacheNode = [CacheMap] | [CacheMap, any]

/**记忆传入的函数，相同的入参只执行一次 - 前缀树方法 
 * - [力扣2630](https://leetcode.cn/problems/memoize-ii)
 * @param fn 需要被记忆的函数
 * @returns 新函数
 * @example
 * let callCount = 0;
 * const memoizedFn = memoize(function (a, b) {
 *	  callCount += 1;
 *    return a + b;
 * })
 * memoizedFn(2, 3) // 5
 * memoizedFn(2, 3) // 5
 * console.log(callCount) // 1 
 */
function memoize<T extends Fn>(fn: T): T {
    /**缓存树 - 当前是根节点，代表无入参时的树以及结果 */
    const cacheRoot: CacheNode = [new Map()]

    return function () {
        /**存储当前遍历到的树节点指针 */
        let node: CacheNode = cacheRoot
        //根据入参，遍历并构造Map树
        for (let param of arguments) {
            const map: CacheMap = node[0]
            //如果发现当前节点的Map中，没有找到这个参数对应的Map键，就需要构建新的节点
            if (!map.has(param)) {
                map.set(param, [new Map()])
            }
            //指针往下移动
            node = map.get(param)!
        }
        // 遍历完毕，需要返回这个节点的结果值 
        //如果当前节点没有返回值，就调用
        if (node.length < 2) { //函数返回值有可能是undefined，所以不能用 node[1] === undefined 来做条件
            node[1] = fn(...arguments)
        }
        // console.log('cache: ', deepClone(cache));
        return node[1]
    } as T
}
export default memoize


//#region ————————————————————————代码测试——————————————————————————————————

//这里填写入参
const inputs = [[], [1], [1], [], [1, 2], [1, 2]] //每次调用的入参
const fn = function (...arr: number[]) { //需要被记忆的函数
    return arr.reduce((a, b) => a + b, 0);
}

//根据入参执行函数，查看结果
let callCount = 0;
const memoizedFn = memoize(function (...params: any[]) {
    callCount++
    return fn(...params)
})
console.log('被记忆函数：\n', fn.toString());
inputs.forEach((k, i) => {
    const res = memoizedFn(...k)
    console.log(`第${i}个输入: fn(${k.join(', ')}) \t 结果`, res, '\t当前fn被调用的次数', callCount);
})
//#endregion

